\documentclass[a4paper,twosides,11pt]{article}

\usepackage{latexsym}
\usepackage[italian]{babel}
\usepackage[latin1]{inputenc}% Encoding, codifica ISO 8859-1
\usepackage[T1]{fontenc}
\usepackage{graphicx}
\author{Marco Bonifazi}

\title{ M.A.G.O. Minimizzazione Aree Grafi Ortogonali}

\frenchspacing % Nessuno spazio dopo il punto di fine periodo

\begin{document}% Inizio del corpo del testo
\maketitle
%\tableofcontents

\section{Il programma M.A.G.O.}
M.A.G.O \`e un'applicazione che permette la 
definizione di strutture di grafi ortogonali e alcune operazioni di 
spostamento dei relativi nodi con il fine di poter gestire diverse modalit\`a 
di minimizzazione delle aree dei grafi stessi.

Il programma definisce quindi le operazioni per la costruzione e la 
rappresentazione di elementi quali nodi, segmenti, archi, piegamento su griglia, 
definendo le relazioni tra di essi.

M.A.G.O. \`e scritto in linguaggio C e consente, in maniera primitiva e per grafi non troppo grandi, la visualizzazione su schermo tramite la libreria grafica
multipiattaforma OpenGl.

\section{Gli elementi primitivi}
In M.A.G.O. \`e possibile creare e gestire i seguenti elementi primitivi di
un grafo ortogonale:

\begin{itemize}
\item Griglie
\item Nodi ``reali''
\item Segmenti
\item Piegamenti
\item Archi
\item Archi ``reali''
\item Grafi
\end{itemize}


Nell'applicazione i significati di piegamento e segmenti
vengono concettualmente uniti in quello chiamato convenzionalmente \textit{nodo}, 
per cui si pu\`o dire, con questa strana terminologia, che in un nodo c'\`e 
un piegamento, in un nodo c'\`e un segmento (o meglio in un nodo c'\`e 
la continuazione, la prosecuzione di due segmenti afferenti).

Con l'accezione \textbf{nodo} si intender\`a quindi definire (se non sia specificato diversamente) un qualsiasi elemento caratterizzato da coordinate
che sia possibile considerare, pensare inserito nella griglia.


\subsection{Le griglie}
Il grafo viene rappresentato immaginandolo disegnato su \textbf{griglie bidimensionali},
ad esempio come su un foglio a quadretti dove le intersezioni tra le linee 
rappresentano punti in cui inserire nodi reali, segmenti, archi, piegamento.
Questi punti di inserimento vengono chiamati \textbf{celle} (\texttt{cells}).

In una cella, che nel programma \`e semplicemente un riferimento ad una lista collegata 
di nodi, possono coesistere diversi nodi secondo i vincoli che sono stati posti al movimento 
di questi.

Come si pu\`o immaginare, ovviamente, non possono ad esempio coesistere due nodi reali 
nella stessa cella.

Oltre i riferimenti alle liste di nodi (matrice bidimensionale di celle), le griglie
memorizzano le loro dimensioni (\texttt{dims}): larghezza \texttt{width} e altezza (\texttt{height}).


\begin{verbatim}
/* Grids */

struct struct_grid {
      int dims[2];           /* Dimensions of the grid */
      list_nodes*** cells;   /* Cells */
};
typedef struct struct_grid grid;
\end{verbatim}

\subsection{I nodi}
I \textbf{nodi} sono tutti gli elementi caratterizzati da:
\begin{itemize}
\item una \textit{posizione} in coordinate (riga, colonna) rispetto alla griglia (\texttt{coords}),
\item un \textit{tipo} che determina se il nodo \`e un \textit{nodo reale} (\texttt{real\_node}: tipo 1), oppure  se \`e un \textit{segmento} (\texttt{segment}: tipo 2) o un \textit{piegamento} (\texttt{bend}: tipo 2).
\item un'insieme (una lista collegata di riferimenti) di nodi \textit{vicini} (\texttt{neighbours}),
\item un \textit{nome} da dare al nodo (ma nell'applicazione i nomi non vengono mai usati per ora)
\item il riferimento a due \textit{nodi reali n1 e n2} che rappresentano gli estremi dell'arco di appartentenza
\end{itemize}

La minimizzazione dei grafi avviene muovendo i nodi sulla griglia, azione che comporter\`a quindi cambiamenti dello stato del nodo (posizione, vicini).

\`E importante sottolineare come sia il concetto di vicinanza a formare i grafi: per \textit{vicinanza} si intende la relazione per cui esiste un percorso del grafo tra due nodi vicini.

\begin{verbatim}
/* Nodes */

struct struct_node {
      int position[2];
      struct list_nodes* neighbours; /* List of neighbours*/
      char* label;
      int type; /* 1: Real node - 2: Bend or segment - */
      int number;
      struct struct_node* n1;
      struct struct_node* n2;
};
typedef struct struct_node node;
\end{verbatim}

\subsection{Nodi reali}
Nell'applicazione i \textbf{nodi reali} sono i nodi nel senso ``tecnico'' del termine, ossia di ``punti'' uniti da archi nei grafi.

Sono una specializzazione del concetto di nodo del programma, hanno tipo 1, hanno i riferimenti n1 e n2 sempre nulli in quanto non sono pensati 
come appartenenti ad un arco ma come estremi ``generatori'' di un arco.

\subsection{Segmenti e piegamenti}
Rappresentano le \textbf{congiunzioni} tra due (e solo due) diversi nodi.

Nel caso dei segmenti, il nodo ha come vicini due nodi sulla stessa retta, nel caso dei piegamenti insieme ai vicini forma un angolo retto.

L'unica differenza consiste nell'impossibilit\`a di spostare i segmenti (e ci\`o \`e implementato verificando che i vicini siano in linea retta).

Anch'essi sono una specializzazione del concetto di nodo del programma, hanno tipo 2.

\subsection{Arco}
Come nel caso dei nodi, si distingue tra in concetto di ``arco'' e ``arco reale''.

Per \textbf{arco} si intende la relazione di vicinanza tra due nodi di due celle vicine.
\begin{verbatim}
/* Arcs */

struct struct_arc{
      node* n1;
      node* n2;
      int degree; /* Number of couple of nodes 
      		   *  with the same positions*/
};
typedef struct struct_arc arc;
\end{verbatim}


\subsection{Archi ``reali''}
Per \textbf{archi ``reali''} si intende la relazione di vicinanza tra due nodi ``reali'' che quindi possono essere in celle lontane tra loro,
ma tramite le quali esiste un percorso di nodi non reali (rappresentato dai nodi estremi e da una lista collegata di nodi del percorso, compresi comunque gli estremi).

\begin{verbatim}
/* Real arcs */

struct list_real_arcs {
      list_nodes* nodes;
      node* n_start;
      node* n_end;
      int length;
      struct list_real_arcs* next;
};
typedef struct list_real_arcs list_real_arcs;

\end{verbatim}

Nel programma gli archi reali vengono utilizzati non come elementi propriamente primitivi e a s\'e stanti,
ma piuttosto nella loro globalit\`a per verificare determinati vincoli di movimento.

Per questo motivo nel programma l'arco reale \`e implementato all'interno della struttura che definisce la lista di archi reali e non a s\'e stante.

\subsection{Grafi}
Il concetto di \textbf{grafo} viene definito dalla totalit\`a delle relazioni di vicinanze tra i nodi.

Quelli che nel programma sono chiamati ``archi reali'' e che sono gli archi del grafo ``tecnicamente parlando'', vengono considerati non come elementi portanti e costruttivi del grafo,
bens\`i come elementi ricavati e che vengono utilizzati per operazioni di verifica. Ci\`o \`e dovuto anche al fatto che non \`e stata pensata ancora l'implementazione di elementi quali
le \textit{facce} dei grafi (\texttt{faces}).

Non esiste un'implementazione diretta del grafo, ma poich\`e ogni nodo ha in s\'e i riferimenti ai vicini \`e possibile dire che ogni nodo rappresenta
per estensione tutto il grafo connesso di cui fa parte (e questo all'atto pratico avviene tramite visite in ampiezza e in profondit\`a).

Nell'applicare la minimizzazione, \`e cura dell'utente verificare che i grafi siano connessi; il programma prender\`a in considerazione solo il grafo connesso 
relativo al primo nodo che incontra a partire dall'angolo Nord Ovest della griglia.


Gli elementi sono manipolabili tramite \textit{operazioni primitive} quali creazione, inserimento nelle relative liste, cancellazione, copia, concatenazione, verifiche etc. per le quali il codice in C \`e autoesplicativo (e ricalca i soliti pezzi di codice di qualsiasi libro o appunto) e tramite 
\textit{operazioni complesse} quali \textit{spostamento}, \textit{retrazione}, \textit{taglio del cappio}, \textit{ribaltamento dell'angolo}.

Le operazioni primitive sono implementate nel file \texttt{elements.c} con relativo header \texttt{elements.h}, mentre le operazioni complesse sono immerse nel modulo
del codice comprendente anche gli algoritmi: \texttt{grafi.c} e \texttt{grafi.h}

\section{Le operazioni complesse}

\subsection{Movimenti dei nodi e vincoli}
Intanto occorre subito precisare che, trattandosi di grafi ortogonali, nell'applicazione non esiste in alcun modo il concetto di movimento in diagonale; per cui un nodo non pu\`o deliberatamente essere fatto saltare da una cella ad un'altra vicina percorrendo la diagonale.
L'unico caso che visivamente fa eccezione a riguardo \`e quello del movimento di un piegamento, che va pensato per\`o come caso particolare di trascinamento di un nodo, come meglio verr\`a precisato.
La generazione di \textit{cappi} \`e evitata durante lo spostamento di piegamenti: in tal caso c'e' infatti fusione sulla base del cappio.

Gli elementi che si possono muovere nella realizzazione dell'algoritmo di minimizzazione sono:
\begin{itemize}
\item Nodi reali
\item Piegamenti
\end{itemize}

I segmenti, quindi, sono elementi che non si possono muovere in quanto \`e presente un controllo sulla posizione delle celle vicine rispetto a quella da spostare.
\`E escluso ai segmenti il movimento in quanto la creazione di \textit{cappi} (\texttt{slipknot}) avrebbe complicato eccessivamente il disegno, ottenendo improbabili 
\textit{facce vuote} all'interno di archi lunghissimi.

Nodi reali e piegamenti possono quindi muoversi unicamente nelle 4 direzioni cardinali, Nord, Est, Sud, Ovest (nel programma \textit{Up, Right, Down, Left}).

Il movimento di un qualsiasi nodo comporta la creazione o cancellazione di segmenti, piegamenti.

\subsubsection{Vincoli ``di cella''}
Nel muovere i nodi reali sono  stati considerati alcuni vincoli arbitrariamente chiamati \textit{''di cella''}; in quanto si esprimono localmente al punto-cella considerato, senza
considerazioni di altro genere, riguardante relazioni pi\`u globali di celle o nodi (contrariamente ad altri tipi di vincoli successivamente elencati).

\begin{itemize}
\item Un nodo reale generalmente (vedi eccezioni qui sotto) non pu\`o muoversi in una cella occupata: quindi una cella occupata da un nodo reale ha un solo nodo nella sua lista, non possono esistere n\'e situazioni omogenee ``nodo reale - nodo reale'', n\'e altre miste ``nodo reale - segmento'' o ``nodo reale - piegamento''.

Esiste infatti, prima del movimento di un nodo reale, un controllo \texttt{int is\_free\_cell( grid* gr, int x, int y)} per la verifica della presenza o meno di nodi nella cella.

\item Un nodo reale pu\`o muoversi in una cella occupata se gli occupanti della cella sono tutti nodi
non reali vicini del nodo in questione.
Ad esempio \`e permesso l'allineamento di un nodo reale nei confronti di due bend disposti a riempire i due angoli retti affiancati.

\item Un nodo reale pu\`o muoversi in una cella occupata se fa ``retrazione'', ossia se il nodo ha un solo vicino e se la cella destinazione \`e occupata proprio dal piegamento o dal segmento vicino del nodo stesso.

\end{itemize}


\subsubsection{Vincoli ``algoritmici''}
Vincoli algoritmici particolari sono posti nel movimento di piegamenti.
In particolare \`e stato introdotta la notazione di \textit{etichettatura} di un nodo, ossia una coppia di nodi reali che rappresentano gli estremi dell'arco reale a cui il nodo appartiene.

I nodi reali ovviamente hanno etichettatura nulla in quanto generano archi, non appartenendovi in senso stretto.

L'applicazione permette di scegliere se ritenere attivo il seguente vincolo nel momento di spostamento di un piegamento (\texttt{verify\_labels}): un nodo non reale pu\`o spostarsi in una cella solo se in tale cella i nodi presenti hanno \texttt{tutti} un nodo reale in comune nell'etichetta (in pratica tutti i nodi della cella appartengono ad archi ``generati'' tutti da uno stesso nodo).

L'assegnazione iniziale delle etichette avviene successivamente alla creazione del grafo:
\begin{itemize}
\item vengono creati gli archi reali (\texttt{create\_list\_arcs}), tramite una visita in profondit\`a con controllo dei nodi visitati per evitare cicli nel grafo,
\item viene fatta l'analisi degli archi reali andando a scandire le liste dei nodi che li compongono: in questa fase avviene l'etichettatura dei nodi (\texttt{assign\_label}).
\end{itemize}

Durante il procedere dei movimenti e quindi la creazione di segmenti e piegamenti, le etichettature vengono assegnate ``al volo'', senza quindi ricreare la lista degli archi reali, ma assegnando direttamente le etichette.


\subsection{Primitive di movimento raggruppate}

Solitamente il movimento avviene per colonne e righe (\texttt{move\_row}, \texttt{move\_column}): \`e possibile spostare la singola colonna verso destra o sinistra, la singola riga verso l'alto o il basso: \textbf{spostamento per spinta}. 

\`E inoltre possibile cercare di spostare una riga verso un'altra riga, una colonna verso un'altra: spostamento \textbf{per attrazione} 

(\texttt{move\_to\_row}, \texttt{move\_to\_column}).

La differenza sta nel fatto che lo spostamento per attrazione prevede una sequenza di movimenti per spinta dall'elemento via via sempre pi\`u vicino al punto di attrazione.

Per esempio, se la colonna pi\`u a sinistra viene ``spinta'' verso destra, allora tutti i nodi sulla prima colonna vengono spostati (se possibile) sulla seconda colonna; tutti i nodi sulla seconda colonna vengono spostati (se possibile) sulla terza colonna; e cos\`{\i} via.
%Ad esempio una \textbf{spinta} dalla prima riga in alto all'ultima riga in basso prevede che tutti i nodi che si possono spostare possano essere fatti scendere riga per riga durante la ``passata'' di un immaginario cursore.

Un'\textbf{attrazione} verso la riga inferiore della griglia prevede il movimento per spinta della prima riga verso l'ultima, della terza verso l'ultima, della quarta verso l'ultima, e cos\`i via, quindi l'attrazione prevede molte scansioni dell'immaginario cursore nella griglia verso il basso.

Ovviamente, nell'algoritmo, \`e assai probabile che un movimento per spinta debba esser fatto ripartire pi\`u frequentemente rispetto a quello per attrazione.

\section{Minimizzazione del grafo}
Una volta presa in pasto una griglia, M.A.G.O. tenta di minimizzarla secondo un algoritmo scelto.

Tale algoritmo pu\`o essere scelto insieme ai comandi di esecuzione, oppure pu\`o essere caricato da un file \texttt{config.conf} nelle cartelle delle griglie di input (un file di configurazione per cartella), insieme ad altri parametri.

Sono stati implementati diversi algoritmi di minimizzazione:

\begin{itemize}

\item \textbf{Spinta all'angolo alternata}: prevede il movimento di righe e colonne in maniera alternata a partire dall'alto e da sinistra, verso l'angolo in basso a destra.

\item \textbf{Accentratore orario}: consiste nell'attrazione verso il centro del grafo. Vengono attratte difatti righe e colonne in maniera ciclica (oraria).
Scendendo nel dettaglio c'\`e un'attrazione da sinistra verso la colonna centrale, poi dall'alto verso la riga centrale, poi da destra verso la colonna centrale, poi da sotto verso la riga centrale e cos\`{\i} via. 

\item \textbf{Accentratore sopra/sotto}: \`e una variazione dell'accentratore orario, in cui l'ordine di attrazione non \`e orario ma sopra-sotto, sinistra-destra

\item \textbf{Attrazione all'angolo alternata}: prevede l'attrazione dei nodi non verso il centro ma verso l'angolo Sud-Est della griglia.

\end{itemize}

Ad ogni passaggio dei rispettivi cicli di attuazione degli algoritmi avviene un'operazione detta di \textit{retrazione} che comporta il taglio dei segmenti ``appesi'' a piegamenti e l'arretramento del relativo nodo.

Per ogni tipo di algoritmo \`e possibile impostare la possibilit\`a di verifica delle etichette.

Qualora attivata la possibilit\`a, le aree delle griglie finali risultano molto maggiori rispetto alle aree delle griglie senza l'attivazione della verifica.


Gli algoritmi non accentratori, risentono di concentrazioni di nodi all'interno di particolari zone della griglia.

Si nota anche come alla minimizzazione spinta di aree consiste generalmente un aumento importante di piegamenti. 


Il programma calcola l'area iniziale e finale, la lunghezza totale del grafo in segmenti e, in maniera imprecisa ma efficace per ordine di grandezza, il tempo di esecuzione.

L'elaborazione in fase di minimizzazione termina quando per un numero fissato di volte (\texttt{MONOPOLYZE\_FACTOR} in \texttt{grafi.h}) l'area non cambia valore.

\section{Installazione}
Una volta ottenuto il file .tar.gz, occorre scompattarlo a piacere in una directory.
Ci sono due diverse opzioni per la compilazione tramite Makefile.

\begin{verbatim}
make grafi_opengl
\end{verbatim}
per la compilazione e l'uso delle librerie OpenGl per la visualizzazione, occorre che sia decommentata la riga
\begin{verbatim}
init_gl(argc, argv, current_grid, current_cfg);
\end{verbatim}
alla fine del file \texttt{grafi.c}


\begin{verbatim}
make grafi
\end{verbatim}
per la compilazione senza OpenGl, per la quale occorre invece commentare la riga suddetta.


Inoltre sono presenti \texttt{make grafi\_opengl\_debug} e  \texttt{make grafi\_debug} per la compilazione con opzione \texttt{-g} di debug.

Infine \texttt{make clean} pu\`o esser lanciato per rimuovere il file eseguibile \texttt{mago} generato.


\section{Esecuzione}
Ecco il comando per eseguire M.A.G.O.:

\begin{verbatim}
./mago graphs\_dir stats_file verify_labels [alghoritm [args]] [opengl_grid]
\end{verbatim}

Rispettivamente:
\begin{itemize}
\item\texttt{graphs\_dir} \`e la directory in cui sono presenti i file di input \texttt{.gr} in cui sono rappresentate le griglie.
\item\texttt{stats\_file} \` un file in cui verranno aggiornate le statistiche relative alla minimizzazione del grafo. Se si desidera la visualizzazione OpenGl del grafo occorre
usare come nome fittizio del file la parola \texttt{opengl}.
\item\texttt{verify\_label} deve essere 0 o 1 nel caso in cui rispettivamente si vogliano considerare o meno i \textit{vincoli di etichetta}.
\item\texttt{alghoritm} \`e un intero che rappresenta l'algoritmo da utilizzare per la mimizzazione del grafo (ad esempio 1 o 2 o 3\dots).
\item\texttt{args} sono eventuali ulteriori argomenti che vanno passati in input in se l'algoritmo scelto lo richiede. Il primo argomento rappresenta il numero di passi che vanno effettuati (volendo si pu\`o fermare l'elaborazione del grafo prima della conclusione naturale della minimizzazione), mettendo un numero alto a piacere (1000000 ad esempio), ci si para da qualsiasi interruzione.
\item\texttt{opengl\_grid} \`e il numero progressivo della griglia tra quelle della directory di input che si desidera visualizzare.
\end{itemize}

Riepilogango, per visualizzare la griglia finale in OpenGl occorre scrivere \texttt{opengl} al posto del file delle statistiche e inserire come ultimo argomento della riga di comando il numero progressivo della griglia che si vuole visualizzare tra le griglie in lettura nella directory di input.

Premendo 'S' durante la visualizzazione in OpenGl \`e possibile ottenere un file \texttt{grafo.pdf} della rappresentazione del grafo.
\subsection{Risultati}
M.A.G.O. opera sulle griglie passate in input (\texttt{load\_grid}) nella cartella \texttt{''graph\_dir''}, le trasforma(\texttt{elaborate\_grid}) e le salva (\texttt{save\_grid}) nella cartella \texttt{"graph\_dir"\_out}.

Inoltre il programma aggiorna il file di statistiche, il cui nome \`e stato passato in input.
Le statistiche sono formattate in maniera semplice da rendere immediata l'importazione da altri applicativi.

In graphs c'\`e una cartella di esempio dove poter giocare coi grafi.

\subsection{Struttura dei file}
\subsubsection{I file delle griglie}
Convenzionalmente occorre pensare i nodi come convenzionalmente numerati in maniera ordinata.
I ``campi'' del file sono rappresentati da:

\begin{itemize}
\item Una riga iniziale che rappresenta il nodo secondo la seguente struttura
\begin{verbatim}
Numero_nodo  Riga  Colonna  Tipo_nodo  Numero_vicini
\end{verbatim}
\item Una serie di riferimenti ai vicini rappresentati dal loro numero identificativo. 
\end{itemize}

Come esempio ecco una parte di uno dei file di griglia
\begin{verbatim}
1 0 0 1 1
                2
2 0 1 1 3
                6
                3
                1
3 0 2 2 2
                4
                2
\end{verbatim}
Che indica come il nodo 1 (posizione 0, 0) abbia come vicino il nodo 2; il nodo 2 (posizione 0, 1) abbia come vicini il nodo 6, il nodo 3 , il nodo 1;
il nodo 3 (posizione 0, 2) abbia come vicini il nodo 4 e il nodo 2.

Il nodo 3 \`e un nodo reale (\`e di tipo 2).

\subsubsection{Il file delle statistiche}

La struttura del file \`e la seguente:
\begin{verbatim}
Area_iniz  Area_fin  Lungh_iniz  Lungh_fin  Tempo_di_esecuzione
\end{verbatim}

\subsubsection{Il file di configurazione}

La struttura del file \`e la seguente:
\begin{verbatim}
Algoritmo  Arg1  Arg2  Arg3
\end{verbatim}

\subsection{I file del progetto}

\begin{itemize}
\item \texttt{grafi.c grafi.h} contengono le primitive complesse di elaborazione dei movimenti e della griglia,
\item \texttt{elements.c elements.h} contengono le primitive per gli elementi dei grafi: nodi, griglie, piegamenti,
\item \texttt{io\_grid.c} contiene le primitive per l'input e output dei file da disco: configurazione, griglia, statistiche,

\item \texttt{grafi\_gl.c grafi\_gl.h} contiene alcune primitive complesse per il calcolo di archi e nodi per la visualizzazione OpenGl,
\item \texttt{\_gl.c} contiene alcune primitive per la visualizzazione OpenGl,
\item \texttt{gl2ps.c gl2ps.h} permette la stampa del grafo, premendo 'S', durante la visualizzazione OpenGl della griglia finale.

\end{itemize}

















\end{document}
   

